package com.lw.leetcode.bingChaJi.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.07. 婴儿名字
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/15 21:39
 */
public class TrulyMostPopular {


    public static void main(String[] args) {
        TrulyMostPopular test = new TrulyMostPopular();

        // [Chris(36), John(27)]
//        String[] names = {"John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"};
//        String[] synonyms = {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"};

        // ["Weusps(79)","Acohsf(86)","Aeax(646)","Gnplfi(109)","Okwuq(96)","Ofl(72)",
        // "Alrksy(69)","Fcclu(70)","Bnea(179)","Qyqifg(85)","Obcbxb(124)","Msyr(211)",
        // "Jvqg(47)","Fpaf(219)","Nuq(61)","Chycnm(253)","Avmzs(39)","Mcnef(59)",
        // "Csh(238)","Hljt(51)","Gbkq(77)","Mwwvj(70)","Drzsnw(87)","Npilye(25)",
        // "Yjc(94)","Oltadg(95)","Dwifi(237)","Unsb(26)","Onnev(77)","Yeekgc(11)",
        // "Dnsay(72)","Uvkdpn(71)","Ibink(32)","Ucqh(51)","Chhmx(259)","Naf(3)",
        // "Knpuq(61)","Nzaz(51)","Nekuam(17)","Ard(82)","Axwtno(57)","Nsgbth(26)",
        // "Kasgmw(95)","Mtz(72)","Ijveol(46)","Qiy(26)","Avcp(41)","Jfq(26)","Kgabb(236)","Koaak(53)","Ntfr(70)","Gauuk(75)",
        // "Hfp(97)","Fvkhz(104)","Ebov(96)","Qbmk(45)","Kufa(95)","Hcvcgc(97)","Dhe(79)"]


        // [Nzaz(51), Uxf(74), Chycnm(253), Meutux(64), Hfp(97), Ijveol(46), Koaak(53), Mwwvj(70), Bnea(179), Ntfr(70), Ommjh(63), Npilye(25), Hrschk(30), Vbp(89), Fcclu(70), Pgfpma(95), Gnplfi(109), Ard(82), Kgabb(236), Weusps(79), Qyqifg(85), Alrksy(69), Avmzs(39), Ibink(32), Qiy(26), Dhe(79), Wpagta(25), Hvueqc(91), Ebov(96), Qnaakk(76), Hljt(51), Gbclj(20), Yjc(94), Ofl(72), Kxutz(5), Okwuq(96), Uzgx(65), Qejo(60), Qsc(48), Owh(64), Owk(87), Hcvcgc(97), Aeax(646), Grqrg(81), Rngl(12), Nsgbth(26), Nuq(61), Qvjp(6), Ucqh(51), Dwayf(97), Uhsg(23), Mcnef(59), Xxmsn(98), Msyr(211), Xjjol(62), Gbkq(77), Ghc(15), Qweye(15), Gauuk(75), Axwtno(57), Chhmx(259), Mtz(72), Jfq(26), Ffwni(67), Avcp(41), Obcbxb(124), Jvqg(47), Wzyyim(34), Qbmk(45), Vgxj(11), Dwifi(237), Fpaf(219), Uwjsu(41), Yeekgc(11), Nekuam(17), Acohsf(86), Tuvzkd(85), Siv(47), Kri(71), Onnev(77), Txixz(87), Csh(238), Wfmspz(39), Oltadg(95), Fvkhz(104), Qxabri(41), Tlv(95), Unsb(26), Qxkjt(31), Uvkdpn(71), Hvia(6), Iidh(64), Kufa(95), Lucf(62), Qoi(70), Dnsay(72), Naf(3), Drzsnw(87), Kasgmw(95), Knpuq(61)]
        String[] names = {"Fcclu(70)", "Ommjh(63)", "Dnsay(60)", "Qbmk(45)", "Unsb(26)", "Gauuk(75)", "Wzyyim(34)", "Bnea(55)", "Kri(71)", "Qnaakk(76)", "Gnplfi(68)", "Hfp(97)", "Qoi(70)", "Ijveol(46)", "Iidh(64)", "Qiy(26)", "Mcnef(59)", "Hvueqc(91)", "Obcbxb(54)", "Dhe(79)", "Jfq(26)", "Uwjsu(41)", "Wfmspz(39)", "Ebov(96)", "Ofl(72)", "Uvkdpn(71)", "Avcp(41)", "Msyr(9)", "Pgfpma(95)", "Vbp(89)", "Koaak(53)", "Qyqifg(85)", "Dwayf(97)", "Oltadg(95)", "Mwwvj(70)", "Uxf(74)", "Qvjp(6)", "Grqrg(81)", "Naf(3)", "Xjjol(62)", "Ibink(32)", "Qxabri(41)", "Ucqh(51)", "Mtz(72)", "Aeax(82)", "Kxutz(5)", "Qweye(15)", "Ard(82)", "Chycnm(4)", "Hcvcgc(97)", "Knpuq(61)", "Yeekgc(11)", "Ntfr(70)", "Lucf(62)", "Uhsg(23)", "Csh(39)", "Txixz(87)", "Kgabb(80)", "Weusps(79)", "Nuq(61)", "Drzsnw(87)", "Xxmsn(98)", "Onnev(77)", "Owh(64)", "Fpaf(46)", "Hvia(6)", "Kufa(95)", "Chhmx(66)", "Avmzs(39)", "Okwuq(96)", "Hrschk(30)", "Ffwni(67)", "Wpagta(25)", "Npilye(14)", "Axwtno(57)", "Qxkjt(31)", "Dwifi(51)", "Kasgmw(95)", "Vgxj(11)", "Nsgbth(26)", "Nzaz(51)", "Owk(87)", "Yjc(94)", "Hljt(21)", "Jvqg(47)", "Alrksy(69)", "Tlv(95)", "Acohsf(86)", "Qejo(60)", "Gbclj(20)", "Nekuam(17)", "Meutux(64)", "Tuvzkd(85)", "Fvkhz(98)", "Rngl(12)", "Gbkq(77)", "Uzgx(65)", "Ghc(15)", "Qsc(48)", "Siv(47)"};
        String[] synonyms = {"(Gnplfi,Qxabri)", "(Uzgx,Siv)", "(Bnea,Lucf)", "(Qnaakk,Msyr)", "(Grqrg,Gbclj)", "(Uhsg,Qejo)", "(Csh,Wpagta)", "(Xjjol,Lucf)", "(Qoi,Obcbxb)", "(Npilye,Vgxj)", "(Aeax,Ghc)", "(Txixz,Ffwni)", "(Qweye,Qsc)", "(Kri,Tuvzkd)", "(Ommjh,Vbp)", "(Pgfpma,Xxmsn)", "(Uhsg,Csh)", "(Qvjp,Kxutz)", "(Qxkjt,Tlv)", "(Wfmspz,Owk)", "(Dwayf,Chycnm)", "(Iidh,Qvjp)", "(Dnsay,Rngl)", "(Qweye,Tlv)", "(Wzyyim,Kxutz)", "(Hvueqc,Qejo)", "(Tlv,Ghc)", "(Hvia,Fvkhz)", "(Msyr,Owk)", "(Hrschk,Hljt)", "(Owh,Gbclj)", "(Dwifi,Uzgx)", "(Iidh,Fpaf)", "(Iidh,Meutux)", "(Txixz,Ghc)", "(Gbclj,Qsc)", "(Kgabb,Tuvzkd)", "(Uwjsu,Grqrg)", "(Vbp,Dwayf)", "(Xxmsn,Chhmx)", "(Uxf,Uzgx)"};

        //

        String[] strings = test.trulyMostPopular(names, synonyms);
        System.out.println(Arrays.toString(strings));


    }

    private Map<String, String> nameMap = new HashMap<>();

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> countMap = new HashMap<>();
        for (String name : names) {
            String[] split = name.split("\\(");
            countMap.put(split[0], Integer.parseInt(split[1].substring(0, split[1].length() - 1)));
        }
        for (String synonym : synonyms) {
            String[] split = synonym.split(",");
            String a = split[0].substring(1);
            String b = split[1].substring(0, split[1].length() - 1);
            String a1 = find(a);
            if (a1.equals(b)) {
                continue;
            }
            String b1 = find(b);
            if (b1.equals(a)) {
                continue;
            }
            if (a1.compareTo(b1) < 0) {
                nameMap.put(b1, a1);
            } else if (a1.compareTo(b1) > 0) {
                nameMap.put(a1, b1);
            }
        }

        Map<String, Integer> map = new HashMap<>();
        for (String key : nameMap.keySet()) {
            String s = find2(key);
            Integer count = map.get(s);
            if (count == null) {
                count = countMap.getOrDefault(s, 0);
            }
            count += countMap.getOrDefault(key, 0);
            map.put(s, count);
        }
        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            if (!nameMap.containsKey(entry.getKey()) && !map.containsKey(entry.getKey())) {
                map.put(entry.getKey(), entry.getValue());
            }
        }
        String[] arr = new String[map.size()];
        int i = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            arr[i++] = entry.getKey() + "(" + entry.getValue() + ")";
        }
        return arr;
    }


    private String find(String value) {
        String next = nameMap.get(value);
        if (next == null) {
            return value;
        }
        String s = find(next);
        if (!s.equals(next)) {
            nameMap.put(next, s);
        }
        return s;
    }

    private String find2(String value) {
        String next = nameMap.get(value);
        if (next == null) {
            return value;
        }
        return find2(next);
    }

}
